public class LinkList {  //不带头节点
    public static class node{
        int val;
        node next;

        public node(int val){
            this.val=val;
            this.next=null;
        }
        public node(int val,node next){
            this.val=val;
            this.next=next;
        }
    }

    public LinkList(){

    }

    public LinkList(int val){
        head=new node(val);
    }
    private node head;

    public void addFist(int val){
        LinkList.node newNode=new node(val);
        newNode.next=head;
        head=newNode;
    }

    public void addLast(int val){
        LinkList.node newNode=new node(val);
        node cur=head;
        while(cur.next!=null){
            cur=cur.next;
        }
        cur.next=newNode;
    }

    public int size(){
        int size=1;
        if(head==null)return 0;
        node cur=head;
        while(cur.next!=null){
            cur=cur.next;
            size++;
        }
        return size;
    }

    public void display(){
        if(head==null)return;
        node cur=head;
        while(cur!=null){
            System.out.print(cur.val+" ");
            cur=cur.next;
        }
        System.out.println();
    }

    public void addIndex(int index,int val){  //在index位置前添加一个值
    if(index<0||index>size()){
        return;
    }
    if (index==size()){
        addLast(val);
        return;
    }
    if(index==0){
        addFist(val);
        return;
    }
    LinkList.node newNode=new node(val);
    node cur=findIndex(index);
    newNode.next=cur.next;
    cur.next=newNode;
    }

    private node findIndex(int index){
        int flag=0;
        node cur=head;
        while(flag!=index-1){
            cur=cur.next;
            flag++;
        }
        return cur;
    }

    public void remove(int key){ //删除值为key的节点
        if(head==null)return;
        if(head.val==key){
            head=head.next;
            return;
        }
        node cur=findKey(key);
        if(cur==null)return;
        cur.next=cur.next.next;
    }
    private node findKey(int key){
        node cur=head;
        while(cur.next!=null){
            if(cur.next.val==key){
            return cur;
            }
            cur=cur.next;
        }
        return null;
    }

    public void removeAllKey(int key){
    if(head==null)return;
    node cur=head.next;
    node prev=head;
    while(cur!=null){
        if(cur.val==key){
            prev.next=cur.next;
              cur=cur.next;
        }else {
            prev=cur;
            cur=cur.next;
        }
    }
    if(head.val==key){
        head=head.next;
    }
    }

    public void claer(){
        node cur=head;
        while(cur!=null){
            node temp=cur.next;
            cur.next=null;
            cur=temp;
        }
        head=null;
    }

    public  node findMid(){
        node low=head;
        node fast=head;
        while(fast!=null){
            fast=fast.next;
           if(fast!=null){
               fast=fast.next;
               low=low.next;
           }else{
               break;
           }
        }
        return low;
    }

}
